perm filename LOSS[CLS,LSP] blob
sn#855070 filedate 1988-03-28 generic text, type C, neo UTF8
COMMENT ā VALID 00034 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002
C00006 00003
C00010 00004 (defun pr-walk (class)
C00012 00005 Class Precedence List
C00022 00006 /sub
C00035 00007 /sub
C00043 00008 (defun pow (class-name)
C00050 00009 (defun preorder-walk (class)
C00051 00010 common-lisp-object-system/su
C00064 00011 (defun print-nodes ()
C00066 00012 (init)
C00067 00013 common-lisp-object-system/su
C00073 00014 (init)
C00075 00015 Hard Cases
C00078 00016 Common-Lisp-Object-system/su
C00083 00017 (topologically-sort 'a)
C00085 00018 common-lisp-object-system/su
C00093 00019 lgd/su
C00094 00020 Moon/su
C00098 00021 moon/su
C00099 00022 moon/su
C00101 00023 common-lisp-object-system/su
C00106 00024 Moon/su
C00108 00025 moon/su
C00110 00026 common-lisp-object-system/su
C00111 00027 common-lisp-object-system/su
C00115 00028 moon
C00118 00029 common-lisp-object-system/su
C00128 00030 gregor.pa@xerox
C00136 00031 common-lisp-object-system/su
C00143 00032 gregor.pa@xerox/su
C00149 00033 common-lisp-object-system/su
C00155 00034 rrrs-authors@mc.lcs.mit/su
C00163 ENDMK
Cā;
(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 () ())
(defclass c6 () ())
(print-nodes)
(topologically-sort 'c1)
(init)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 () ())
(compute-total-order 'c1)
(cpl-less 'c5 'c6)
(cpl-less 'c6 'c5)
*lattice*
*local-info*
(compute-alpha-paths 'c1 *lattice*)
(defun init-local-info (node)
(setf (root *local-info*) node)
(setf (total-order *local-info*) ())
(setf (lattice *local-info*) *lattice*)
(compute-alphabetical-paths *local-info*)
node)
(init-local-info 'c1)
*local-info*
(cpl-less 'c3 'c5)
(in-lattice-order 'c6 'c5)
(in-local-precedence-order 'c6 'c5)
(untrace)
(trace in-kleene-brouwer-order)
(all-nodes *lattice*)
(alphabetical-paths *local-info*)
(*catch 'foo (*throw 'foo 'baz))
(defun cpl-less (node1 node2)
(cond ((eq node1 node2) nil)
(t (let ((p (cpl-less-1 node1 node2)))
(cond ((or (and (in-lattice-order node1 node2)
(in-local-precedence-order node2 node1))
(and (in-lattice-order node2 node1)
(in-local-precedence-order node1 node2))
(eq p (cpl-less-1 node2 node1)))
(error '|Inconsistent Lattice|)
(*throw 'inconsistent-lattice nil))
(t p))))))
(DEFCLASS C1 () ())
(DEFCLASS C2 () ())
(DEFCLASS C3 () ())
(DEFCLASS C4 (C1 C2) ())
(DEFCLASS C5 (C3 C2) ())
(DEFCLASS C6 (C4 C5) ())
(compute-total-order 'c6)
(defun print-nodes ()
(do ((nodes *node-alist* (cdr nodes)))
((null nodes))
(let ((nr (node-record (car nodes))))
(print `(,(name nr) (count = ,(count nr)) (pseudo-order = ,(pseudo-order nr))
(in-degree ,(in-degree nr))
(superclasses
,(do ((l (direct-superclasses nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans)))
(successor-supers
,(do ((l (top-supers nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans)))
(successor-siblings
,(do ((l (top-siblings nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans))))))))
(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(let ((*preorder-counter* 0))
(preorder-walk (find-node-record 'c1)))
(print-nodes)
(topologically-sort 'c1)
= (C1 C2 C3 C4 C6 C5 TOP)
(init)
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort 'c2)
= (C2 C3 C5 C4 C6 TOP)
(init)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 (top) ())
(topologically-sort)
= Inconsistent Lattice
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(topologically-sort)
= (C6 C4 C5 C1 C3 C2 TOP)
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort)
= Inconsistent Lattice
(init)
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
(topologically-sort 'e7)
= (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3)
(init)
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit (food) ())
(defclass spice (food) ())
(defclass food () ())
(defclass pie (apple cinnamon) ())
;(defclass pastry (cinnamon apple) ())
(topologically-sort 'pastry)
(init)
(defclass pie (apple cinnamon) ())
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit () ())
(defclass spice () ())
(topologically-sort 'pie)
(defun pr-walk (class)
(push (name class) *pre*)
(dolist (superclass (direct-superclasses class))
(pr-walk superclass)))
(defun pw-rear (class-name)
(let ((*pre* nil))
(pr-walk (find-node-record class-name))
(let ((ans ()))
(do ((pre *pre* (cdr pre)))
((null pre) ans)
(unless (memq (car pre) ans) (push (car pre) ans))))))
(defun pw-front (class-name)
(let ((*pre* nil))
(pr-walk (find-node-record class-name))
(let ((ans ()))
(do ((pre (reverse *pre*) (cdr pre)))
((null pre) (reverse ans))
(unless (memq (car pre) ans) (push (car pre) ans))))))
(pw-front 'e7)
(init)
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
Class Precedence List
I've been searching for a way to explain the class precedence
list computation that is simpler than the existing explanations.
I think it can be explained like this:
We will compute the total order on classes at or above the class, C. Call
the top of the class lattice TOP. Let CL be the set of classes at or
above C. Sort this set according to the relation, <, defined as follows:
Consider C1 and C2 in CL.
1. If there exists a path, P, from C to TOP such that
C1 and C2 are in P, then C1<C2 iff C1 is closer to C
along P. [This is the lattice order.]
2. If C1 and C2 are direct superclasses of C3, where C3 is
in CL, then C1<C2 iff C1 precedes C2 in the local precedence
list for C3. [This is the local precedence order.]
3. Let P1 be the alphabetically least path from C to TOP containing C1.
Let P2 be the alphabetically least path from C to TOP containing C2.
Let C3 and C4 be the first classes in P1 and P2, resp, that differ.
Then C1<C2 if C3<C4.
[This is the Kleene-Brouwer order.]
We will say that there is no total order on a set of classes, CL, above a
class C if there exists two classes C1 and C2 in CL such that C1<C2 and
C2<C1 under this order or if clauses 1. and 2. yield inconsistent results.
That is, there is no total order if the lattice order and local
precedence orders contradict each other immediately or if the overall
relationship is inconsistent. (These two cases are separate because
we want to say that the relation is indifferent as to whether the lattice
order or local precedence order is tested first, but an algorithm
tests one before the other. Note the ``if and only if''s in clauses
1 and 2.)
Before I explain some of the terminology more thoroughly, let me point out
that the order defined by 1 and 3 is called the Kleene-Brouwer ordering on
finite trees. This is good, because it is a well-known ordering, and the
class precedence list is computed using a natural extension to it.
A path from C1 to C2 is defined to be an ordered set of classes CL1...CLn,
such that C1=CL1, C2=CLn, and for every i=1...n-1, CL(i+1) is a direct
superclass of CLi.
We say that a class C is in a path P={C1...Cn} if C=Ci for some i between
1 and n, inclusive.
Let P={C1...Cn} be a path from C1 to Cn. Then we say that C3 is closer to
C1 than C4 in P if there exists a Ci and Cj such that Ci is in P, Cj is in
P,C3=Ci, C4=Cj, and i<j. We extend this terminology in the natural way: we
say that C is the first class in the path P that satisfies some predicate,
PR, to mean that there exists a Ci in P such that PR(Ci) is true and that
if 0<j<i, PR(Cj) is not true.
Let P1={D1...Dn} and P2={E1...Em} be paths from C1 to C2. Note that
D1=E1=C1 and Dn=Em=C2. We say that P1 is alphabetically less than P2 if
P1 and P2 are different and if the following is true:
Let Di and Ei be the first classes in P1 and P2, resp, that
differ. Note that 1<i<n, 1<i<m, and D(i-1)=E(i-1). The
condition is that Di precedes Ei in the local precedence order
for D(i-1).
(This might sound complex, but you can generate the paths in alphabetical
order by doing a depth-first traversal of the tree from C1 to C2, collecting
the paths as you go.)
I think this is simpler because the lattice order and local precedence
have an obvious role in the total order. Also, the Kleene-Brouwer order
depends on looking at the least paths through the classes in question,
which depends on the lattice and local precedence orders, and seeing how
the first different classes in those two paths differ. The effect of the
Kleene-Brouwer condition is to impose an alphabetical order on the
lattice in a natural way.
I think people can understand the relation so defined, and it is easier to
invoke an explicit sorting operation rather than blending the sort with
the computation of the relation, as earlier attempts at it explaining the
computation of the total do.
Of course, I hacked this up (though not very elegantly) and it works well
on the one or two examples I ran it on.
If you want to know what it does on some lattice, send me a note
with a class lattice that is in this syntax and I'll run it:
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 () ())
(defclass c6 () ())
(compute-total-order 'c1) = (C1 C2 C3 C4 C6 C5)
(compute-total-order 'c2) = (C2 C3 C5 C4 C6)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 () ())
(compute-total-order 'c1) = Inconsistent Lattice
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(compute-total-order 'c6) = (C6 C4 C1 C5 C3 C2)
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(compute-total-order 'd6) = Inconsistent Lattice
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
(compute-total-order 'e7) = (E7 E5 C1 E6 E4 C2 E3 C3 E2 E1)
The correct answer is (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3).
(compute-total-order 'e7)
(cpl-less 'c3 'c1)
(compare 'c1 'c3)
(E7 E5 E6 E4 E3 E2 E1 C3 C1 C2)
(cpl-less 'c1 'c2)
(cpl-less 'c2 'c3)
(trace in-kleene-brouwer-order)
(untrace)
(compare 'c3 'e2)
(compare 'e2 'c3)
(trace compare)
(compare 'c1 'c3)
(E7 E5 E6 E4 E3 C3 E2 E1 C1 C2)
(init)
(defclass pie (apple cinnamon) ())
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit () ())
(defclass spice () ())
(compute-total-order 'pie)
/sub
common-lisp-object-system
Class Precedence List
This message is long because there are a lot of examples of code running
at the end.
I've been searching for a way to explain the class precedence list
computation that is simpler than the existing explanations. I think we
can explain it fairly well if we relax, a bit, the requirements of
implementations, though we can certainly recommend that implementations go
the extra distance. What I'm proposing is a subset of the behavior that
the Moon algorithm has, but it is simple to explain and understand.
Here it is. We represent a partial order as a set of pairs, (x,y), such
that (x,y) indicates that x<y. Here are the assumed rules of the relation
<.
If x<y and y<z then x<z (transitivity)
If x<y then it is not the case that y<x (asymmetry)
It is not the case that x<x (irreflexivity)
If x<y we'll say that ``x precedes y.'' We then define a partial order on
the components of a class, C1, as follows. Let CL be the components of C1.
If D is a direct superclass of C, where C is in CL, then (C,D) is in the
partial order. If D1 and D2 are direct superclasses of C, where C is in
CL, such that D1 precedes D2 in the local precedence order, then
(D1,D2) is in the partial order. (Note, these correspond to Moon's rules 1
and 2, but we explicitly list the pairs of relations, and we deal with
direct superclasses only.)
Now we topologically sort the elements of CL. This is done as follows.
Select a class C that is not preceded by any other. Put it first in the order.
Remove C from CL and remove all pairs that mention it. This new CL is again
partially ordered by the new pairs. Select a C that is not preceded by
any other and put it next in the order. Continue until CL is empty.
The only way that the algorithm could fail, if there really was a partial
order to start with, would be if there were elements in CL at some point
and every C in CL was preceded by another. If this were true, we could
construct an arbitrary sequence, C1, C2, ... such that Cj+1<Cj. By
transitivity, for all j,k s.t. j<k, Ck<Cj, which implies that Cj is not
equal to Ck. But CL is finite, so some Cj=Ck for some j,k s.t. j<k. This
is a contradiction.
So, if the algorithm fails, we did not have a partial order, which means that
the local precedence order and the lattice order are inconsistent. The algorithm
does signal an error when this happens.
Topological sort runs in C1*M+C2*N time where M is the number of ordered pairs
and N is the number of objects in CL, C1 and C2 some constants.
I hacked this together, and it is 27 lines of code once the data structure
is built. Building the data structure incrementally from a series of
DEFCLASS1's as Moon uses in his examples is another 25 lines of so of code.
The total file is 84 lines long, including the DEFSTRUCT and the code to
make MacLisp think it's Common Lisp enough to run the rest (blush, I
have no Common Lisp to use on SAIL).
The code is an approximate translation of Knuth's algorithm on page 262 of
vol 1 (first edition). It takes the precise DEFCLASS's that define the
sublattice, but it's intended to only illustrate the algorithm at work.
If there are several total orders, the result of the topological sort depends
on the order that the algorithm selects classes that are not preceded by
any others. This depends, generally, on the order that the DEFCLASS's were
evaluated.
I propose that we require implementations to select a total order using an
implementation of topological sort, and that we encourage implementations
to signal an error when several total orders are possible. They can do
this using Moon's algorithm, for example, or by using the topological sort
and having the program notice when there are several classes not preceded
by others from which to select. It could backtrack and determine all of
them, I suppose.
I think this is simpler because many people know topological sort already,
they can understand the partial order in terms of these simple pairs, and
the topological sort algorithm can be explained in a paragraph. People can
also easily see where the non-determinism comes in if there are several
total orders. (Note that most people would know the algorithm after
reading the specification of the partial order as those pairs and seeing
the phrase ``now topologically sort.'')
Here it is running on some examples Moon, Danny, Gregor, and who knows who
else sent out (notice I changed the name of DEFCLASS1 to DEFCLASS). TOP
means the top of the lattice.
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort) = (C1 C2 C3 C4 C6 C5 TOP)
;;; Here are the partial order defining pairs for the above example:
;;; (c1,c2)(c1,c6)(c1,c5)(c2,c6)(c6,c5)(c2,c3)(c2,c4)(c3,c4)
;;; (c3,c5)(c4,c6)(c5,top)(c6,top)
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort) = (C2 C3 C5 C4 C6 TOP)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 (top) ())
(topologically-sort) = Inconsistent Lattice
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(topologically-sort) = (C6 C4 C5 C1 C3 C2 TOP)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort) = Inconsistent Lattice
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
(topologically-sort) = (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass d1 (c1) ())
(defclass d2 (c2) ())
(defclass e1 (d1 d2) ())
(topologically-sort) = (E1 D1 D2 C1 C2 TOP)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
(topologically-sort) = (E1 D1 D2 C1 C3 C2 TOP)
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort) = Inconsistent Lattice
(defclass o (top) ())
(defclass b1 (o) ())
(defclass b2 (o) ())
(defclass b3 (o) ())
(defclass b4 (o) ())
(defclass ex1-1 (b1 b3 b4) ())
(defclass ex1-2 (b2 b3) ())
(defclass example-1 (ex1-1 ex1-2) ())
(topologically-sort) = (EXAMPLE-1 EX1-1 EX1-2 B1 B2 B3 B4 O TOP)
(defclass o (top) ())
(defclass b1 (o) ())
(defclass b2 (o) ())
(defclass b3 (o) ())
(defclass ex2-1 (b1) ())
(defclass ex2-2 (b2) ())
(defclass ex2-3 (b3) ())
(defclass example-2 (ex2-1 ex2-2 ex2-3) ())
(topologically-sort) = (EXAMPLE-2 EX2-1 EX2-2 B1 EX2-3 B2 B3 O TOP)
(defclass d0 (top) ())
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass e (d0 d1) ())
(defclass f (d1 d2 d3) ())
(defclass g (d1 d2) ())
(defclass h (d0) ())
(defclass foo (e f g h) ())
(topologically-sort) = (FOO E F G H D0 D1 D2 D3 TOP)
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass d4 (d3 d2) ())
(defclass d5 (d2) ())
(defclass d6 (d3 d2 d5 d4) ())
(topologically-sort) = Inconsistent Lattice
(defclass g1 (top) ())
(defclass g2 (top) ())
(defclass g3 (top) ())
(defclass g4 (top) ())
(defclass g5 (g1 g2) ())
(defclass g6 (g2 g3) ())
(defclass g7 (g3 g4) ())
(defclass g8 (g4 g5 g6 g7) ())
(topologically-sort) = Inconsistent Lattice
(defclass this (is much) ())
(defclass is (too) ())
(defclass much (fun!) ())
(defclass too () ())
(defclass fun! () ())
(topologically-sort) = (THIS IS TOO MUCH FUN!)
-rpg-
/sub
common-lisp-object-system
Very Dull Message About Class Precedence Lists
For those who are actively thinking about this issue, here is a followup
on my last message about topological sort. It mostly contains a bunch of
runs of a slightly modified algorithm. The modifications are that it now
reports when multiple orders are possible, and, when there is a choice
between several classes with no predecessors, the algorithm selects the
one that appear first in a preorder treewalk from the class for which the
class precedence list is being computed to the top of the lattice (viewed
as a tree). I believe that this algorithm produces the same results as
the New Flavors algorithm, but it is easier to explain: 1. Compute the
partial order relations; 2. topologically sort; 3. when topological sort
has a choice of several classes to put next, select according to preorder.
(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort 'c1)
= (C1 C2 C3 C4 C6 C5 TOP)
(init)
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort 'c2)
= (C2 C3 C5 C4 C6 TOP) Multiple orders possible
(init)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 (top) ())
(topologically-sort 'c1)
= Inconsistent Lattice
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(topologically-sort 'c6)
= (C6 C4 C1 C5 C3 C2 TOP) Multiple orders possible
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort 'd6)
= Inconsistent Lattice
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
(topologically-sort 'e7)
= (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3 TOP)
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass d1 (c1) ())
(defclass d2 (c2) ())
(defclass e1 (d1 d2) ())
(topologically-sort 'e1)
= (E1 D1 C1 D2 C2 TOP) Multiple orders possible
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
(topologically-sort 'e1)
= (E1 D1 D2 C1 C2 C3 TOP) Multiple orders possible
(init)
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort 'd6)
= Inconsistent Lattice
(init)
(defclass b1 (top) ())
(defclass b2 (top) ())
(defclass b3 (top) ())
(defclass b4 (top) ())
(defclass ex1-1 (b1 b3 b4) ())
(defclass ex1-2 (b2 b3) ())
(defclass example-1 (ex1-1 ex1-2) ())
(topologically-sort 'example-1)
= (EXAMPLE-1 EX1-1 B1 EX1-2 B2 B3 B4 TOP) Multiple orders possible
(init)
(defclass b1 (top) ())
(defclass b2 (top) ())
(defclass b3 (top) ())
(defclass ex2-1 (b1) ())
(defclass ex2-2 (b2) ())
(defclass ex2-3 (b3) ())
(defclass example-2 (ex2-1 ex2-2 ex2-3) ())
(topologically-sort 'example-2)
= (EXAMPLE-2 EX2-1 B1 EX2-2 B2 EX2-3 B3 TOP) Multiple orders possible
(init)
(defclass d0 (top) ())
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass e (d0 d1) ())
(defclass f (d1 d2 d3) ())
(defclass g (d1 d2) ())
(defclass h (d0) ())
(defclass foo (e f g h) ())
(topologically-sort 'foo)
= (FOO E F G H D0 D1 D2 D3 TOP)
(init)
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass d4 (d3 d2) ())
(defclass d5 (d2) ())
(defclass d6 (d3 d2 d5 d4) ())
(topologically-sort 'd6)
= Inconsistent Lattice
(init)
(defclass g1 (top) ())
(defclass g2 (top) ())
(defclass g3 (top) ())
(defclass g4 (top) ())
(defclass g5 (g1 g2) ())
(defclass g6 (g2 g3) ())
(defclass g7 (g3 g4) ())
(defclass g8 (g4 g5 g6 g7) ())
(topologically-sort 'g8)
= Inconsistent Lattice
(init)
(defclass this (is much) ())
(defclass is (too) ())
(defclass much (fun!) ())
(defclass too (top) ())
(defclass fun! (top) ())
(topologically-sort 'this)
= (THIS IS TOO MUCH FUN!) Multiple orders possible
-rpg-
(defun pow (class-name)
(let ((*preorder-counter* 0))
(preorder-walk (find-node-record class-name))))
(defun preorder-walk (class)
(traverse class))
(defun traverse (class)
(visit class)
(walk class))
(defun visit (class)
(setf (pseudo-order class) (incf *preorder-counter*)))
(defun walk (class)
(visit class)
; (dolist (superclass (direct-superclasses class))
; (visit superclass))
(dolist (superclass (direct-superclasses class))
(walk superclass)))
(defun rem-dup (l)
(cond ((null l) ())
((memq (car l) (cdr l)) (rem-dup (cdr l)))
(t (cons (car l) (rem-dup (cdr l))))))
(defun tr (class-name)
(let ((*pt* ())
(class (find-node-record class-name)))
(visit1 class)
(talk class)
(reverse (rem-dup *pt*))))
(rem-dup (reverse *pt*))))
(defun visit1 (class)
(push (name class) *pt*))
(defun talk (class)
(dolist (superclass (direct-superclasses class))
(visit1 superclass))
(dolist (superclass (direct-superclasses class))
(talk superclass))))
(defun test ()
(init)
(eval (subst () () '(DEFCLASS PPTEST1 (PPTEST-MIXIN PPTEST2 PPTEST3) ())))
(eval (subst () () '(DEFCLASS PPTEST-MIXIN (PPTEST3) ()) ))
(eval (subst () () '(DEFCLASS PPTEST2 (PPTEST-INTERMEDIATE-1) ())))
(eval (subst () () '(DEFCLASS PPTEST3 (PPTEST-INTERMEDIATE-2) ())))
(eval (subst () () '(DEFCLASS PPTEST-INTERMEDIATE-1 (PPTEST-BASE) ())))
(eval (subst () () '(DEFCLASS PPTEST-INTERMEDIATE-2 (PPTEST-BASE) ())))
(eval (subst () () '(DEFCLASS PPTEST-BASE () ())))
(topologically-sort 'pptest1)
)
ppltiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
(init)
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
(topologically-sort 'ptest1)
Multiple Total Orders Possible
(PTEST1 PTEST2 PTEST3 PTEST4 PTEST5)
(print-nodes)
(PPTEST-BASE (COUNT = 2) (PSEUDO-ORDER = 22) (SUPERCLASSES NIL) (SUCCESSORS
NIL))
(PPTEST-INTERMEDIATE-2 (COUNT = 1) (PSEUDO-ORDER = 20) (SUPERCLASSES (PPTEST-BASE))
(SUCCESSORS (PPTEST-BASE)))
(PPTEST-INTERMEDIATE-1 (COUNT = 1) (PSEUDO-ORDER = 15) (SUPERCLASSES (PPTEST-BASE))
(SUCCESSORS (PPTEST-BASE)))
(PPTEST3 (COUNT = 3) (PSEUDO-ORDER = 18) (SUPERCLASSES (PPTEST-INTERMEDIATE-2))
(SUCCESSORS (PPTEST-INTERMEDIATE-2)))
(PPTEST2 (COUNT = 2) (PSEUDO-ORDER = 13) (SUPERCLASSES (PPTEST-INTERMEDIATE-1))
(SUCCESSORS (PPTEST-INTERMEDIATE-1 PPTEST3)))
(PPTEST-MIXIN (COUNT = 1) (PSEUDO-ORDER = 6) (SUPERCLASSES (PPTEST3)) (SUCCESSORS
(PPTEST3 PPTEST2)))
(PPTEST1 (COUNT = 0) (PSEUDO-ORDER = 2) (SUPERCLASSES (PPTEST-MIXIN PPTEST2
PPTEST3)) (SUCCESSORS (PPTEST3 PPTEST2 PPTEST-MIXIN)))
NIL
(defun order (class-name)
(let ((*cl* ()))
(order1 (find-node-record class-name))
(sortcar
(mapcar #'(lambda (x)(cons (cdr x)(car x))) *cl*)
#'lessp)))
(defun order1 (class)
(unless (assq (name class) *cl*)
(push (cons (name class) (pseudo-order class)) *cl*))
(dolist (super (direct-superclasses class))
(order1 super)))
(ORDER 'pptest1)
((2 . PPTEST1) (6 . PPTEST-MIXIN) (13 . PPTEST2) (15 .
PPTEST-INTERMEDIATE-1) (18 . PPTEST3) (20 . PPTEST-INTERMEDIATE-2) (22 .
PPTEST-BASE))
((1 . PPTEST1) (2 . PPTEST-MIXIN) (3 . PPTEST2) (5 . PPTEST3) (8 . PPTEST-INTERMEDIATE-1)
(10 . PPTEST-INTERMEDIATE-2) (11 . PPTEST-BASE))
Multiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST3 PPTEST-INTERMEDIATE-1
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
Multiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
Multiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
(defun preorder-walk (class)
(cond ((< (pseudo-order class) 0))
(t
(dolist (superclass (reverse (direct-superclasses class)))
(preorder-walk superclass))
(setf (pseudo-order class) (decf *preorder-counter*))
)))
Multiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
common-lisp-object-system/su
CPL Computation
As I've mentioned earlier, I wasn't interested in proposing a new
definition of the CPL computation different from what Flavors presents but
in proposing a clear way of describing it.
I took Moon's suggestion and looked for a different ``tiebreaker'' from
preorder treewalk. I have a simple way to describe it, but the naive
implementation has bad running behavior. The fast version is describable,
but the description is horrendous. I think we want to consider what this
all means once the algorithms are presented.
The algorithm is precisely as before, but when the topological sort would
nondeterministically select one class from among a set of equally good
ones, you choose based on a last-visited preorder treewalk.
A last-visited preorder treewalk is defined in terms of the order in which
classes are visited while performing a process called ``walking from a
class.'' The following is a recursive definition of walking from a class.
Let C be a class and let {C1...Cn} be its direct superclasses in the local
precedence order. To walk from C, first C is visited, then we walk from
C1, then we walk from C2, and so on until we finally walk from Cn.
If a class has been visited before, you ignore that visit. That is,
the order is the order in which the last visits to a node are made.
Normally, one computes the preorder treewalk order as a number attached to
the class. Again normally, this number is computed by performing the
preorder treewalk and INCFing a counter. In a preorder treewalk, when a
class already has a preorder number, you do not re-visit that class; the
modification to normal preorder treewalk to obtain last-visited preorder
treewalk is to eliminate this last pruning. The tiebreaker simply looks
at these preorder numbers, choosing the class with the smallest preorder
number.
Notice that a lot of pruning might have been done by the original preorder
walk and that the last-visited preorder walk eliminates all of the
pruning.
Here is some crufty code to compute the normal preorder number into
a slot of the class called the PREORDER:
(defun preorder-walk (class)
(cond ((< 0 (preorder class))) ;already visited
(t (setf (preorder class) (incf *preorder-counter*))
(dolist (superclass (direct-superclasses class))
(preorder-walk superclass)))))
Here is the modified code:
(defun lv-preorder-walk (class)
(setf (preorder class) (incf *preorder-counter*))
(dolist (superclass (direct-superclasses class))
(lv-preorder-walk superclass)))
This is, of course, less efficient than the previous code, though it looks
simpler. One can get a fast algorithm by doing what could be called a
reversed reversed postorder treewalk (``moonwalk,'' for short).
We define reversed postorder treewalk and then modify that to be reversed
reversed postorder treewalk.
A reversed postorder treewalk is defined in terms of the order in which
classes are visited while performing a process called ``walking from a
class.'' The following is a recursive definition of walking from a class.
Let C be a class and let {C1...Cn} be its direct superclasses in the local
precedence order. Classes are visited unless they have already been
visited. To walk from C, first we walk from Cn, then we walk from Cn-1,
and so on until we finally walk from C1. Finally we visit C. A reversed
reversed postorder treewalk visits classes in precisely the reverse order
that they are visited in a reversed postorder treewalk.
Implementationally, moonwalk isn't too bad. You place reversed postorder
numbers on each class at or above the class of interest, and ties are
broken by selecting the class with the largest reversed postorder number
(note that we chose the smallest number in the preorder tiebreaker).
Selecting the largest effects the second reversing.
Here is the code to do this:
(defun walk (class)
(cond ((< 0 (rpostorder class)))
(t (dolist (superclass (reverse (direct-superclasses class)))
(walk superclass))
(setf (rpostorder class) (incf *counter*)))))
This algorithm works on all of the examples I sent before plus the
two killers Moon sent Sunday.
The question now becomes: Is this what we really want? I claim that
it doesn't matter too much what the tiebreaker is, because it is always
possible to reformulate the lattice and use direct superclasses to
achieve the desired effect. The fact the there are millions of flavors
that use the moonwalk tiebreaker doesn't support the claim that
the moonwalk tiebreaker is right: Perhaps the flavors have been carefully
crafted to inherit properly.
The explicit local precedence orders are the means by which programmers
specify the ordering they want. The tiebreaker simply makes the total
order well-defined. The tiebreaker is not intended to be a ``model''
of the class precedence list. If the topological sort produces a unique
order, that order is intuitive; the cases where tiebreaking happens is
ad hoc and is no intuitive.
In the spirit of trying to figure out the New Flavors algorithm in order
to be able to present it well, my algorithms wizard and I have tried come
up with a more easily explainable algorithm that mimics the New Flavors
and does not have topological sort as an explicit part of it. We failed,
though we have not yet written down an example for which it fails.
[I only mention this because I promised to show this algorithm in my last
message.]
Finally, I'm not sure that the first of Moon's killers has a very intuitive
Flavors order. Here it is again:
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
The Flavors order is (ptest1 ptest2 ptest3 ptest4 ptest5).
Why is ptest4 before ptest5? Here's what the thing looks like:
top------
| |
pt4 |
| |
|-----------pt5
| | /
pt2 pt3 /
\ | /
\ | /
pt1
pt5 is a direct superclass of pt1 and pt4 isn't. One could argue that pt5
is the last of the direct superclasses, so it should come after the
earlier direct superclasses and all of their superclasses; in this case
you get to pt4 first because it is above pt3, which precedes pt5. But,
does being mentioned first in a defclass count for anything? If so, you
get to pt5 by passing through the first of the direct superclasses of pt1
(pt1 to pt2 to pt5) whereas you get to pt4 by passing through the second
of the direct supeclasses of pt1 (pt1 to pt3 to pt4), and there are
exactly the same number of intermediate classes. Everything says pt5
should precede pt4, but Flavors doesn't. I believe this to be a serious
problem.
Finally, my algorithms wizard and I studied the New Flavors CPL
computation description and think there is a performance problem with the
algorithm it describes. Consider the following graph of 4n+1 classes:
(defclass Ai (Bi Ci) ())
(defclass Bi (Di Ai+1) ())
(defclass Ci (Di) ())
(defclass Di () ())
for 0 <= i < n.
Here are the classes for n=2.
(defclass a0 (b0 c0) ())
(defclass b0 (d0 a1) ())
(defclass c0 (d0) ())
(defclass d0 () ())
(defclass a1 (b1 c1) ())
(defclass b1 (d1 a2) ())
(defclass c1 (d1) ())
(defclass d1 () ())
The New Flavors algorithm, as described, seems to take n+1 passes, though
there is exactly one total order possible.
Given that reversed reversed postorder treewalk (or last-visited preorder)
is the tiebreaker, that there is at least one suspicious Flavors-order
example, that people can formulate their lattices as they want to get the
right inheritance, that there is no intuition to any order beyond what the
topological sort gives you, and there is a possible performance problem
with the algorithm described in the New Flavors document, I have now
flipped my bit on this issue from wanting to mimic the Flavors order
to insisting on preorder tiebreaker with topological sort.
-rpg-
(defun print-nodes ()
(do ((nodes *node-alist* (cdr nodes)))
((null nodes))
(let ((nr (node-record (car nodes))))
(print `(,(name nr) (count = ,(count nr))
(superclasses
,(do ((l (direct-superclasses nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans)))
(siblings
,(do ((l (direct-siblings nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans))))))))
(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(walk 'c1)
((WALKING E7) (COUNT 0))
((WALKING E5) (COUNT 0))
((WALKING C1) (COUNT 1))
((WALKING C2) (COUNT 3))
((WALKING E6) (COUNT 0))
((WALKING C2) (COUNT 2))
((WALKING C3) (COUNT 2))
((WALKING E4) (COUNT 0))
((WALKING E3) (COUNT 0))
((WALKING C3) (COUNT 1))
((WALKING E2) (COUNT 0))
((WALKING C2) (COUNT 1))
((WALKING E1) (COUNT 0))
((WALKING C1) (COUNT 0))
((WALKING TOP) (COUNT 2))
(E7 E5 E6 E4 E3 E2 E1 C1)
(init)
(defclass a0 (b0 c0) ())
(defclass b0 (d0 a1) ())
(defclass c0 (d0) ())
(defclass d0 () ())
(defclass a1 () ())
(defclass y (a0) ())
(defclass w (x y z) ())
(topologically-sort 'w)
(init)
(defclass a0 (b0 c0) ())
(defclass b0 (d0 p) ())
(defclass c0 (d0 q) ())
(defclass d0 () ())
(defclass y (a0) ())
(defclass w (x y z) ())
(defclass p (p1 p2 p3) ())
(defclass q (q1 q2 q3) ())
(topologically-sort 'w)
common-lisp-object-system/su
Elaboration on the Non-intuitiveness of New Flavors Algorithm...
...and other related issues.
Remember the funny little configuration of classes mentioned
in an earlier message
(defclass Ai (Bi Ci) ())
(defclass Bi (Di Ai+1) ())
(defclass Ci (Di) ())
(defclass Di () ())
for 0 <= i < n.
Here's what it looks like:
A1
D0 /
| \ /
| \/
| /\
| / \
B0 C0
\ /
\ /
\/
A0
Suppose we are following the New Flavors description of how to compute the
CPL for A0. We start walking through this in depth-first manner starting
at A0. We visit/output A0, visit/output B0, visit D0, visit A1,
visit/output C0, and then visit/output D0. There is no path in depth-first
order with which to get to A1 again, so the first depth-first pass is
over. We notice A1 has not been output and walk it again, outputting A1
last. If A1 is the root of another copy of this, we cannot visit up
through it on the first pass.
If there are classes to the right of A0, they wil be visited and probably
output during the first pass. When the second pass is made, A1 will
be output.
Let's call this configuration the ``MeLast.''
Now consider the following configuration:
T1 T2 T3
| | |
D E F
\ | /
\ | /
\ | /
\|/
C
where C is a class and T1, T2, T3 are independent lattices, except for a
common top. What does intuition say? It says that all of T1 should be
together, all of T2 should be together, and all of T3 should be together,
each group in in some order relative to one another, and the order within
each group unknown. One could argue T1 should precede T2 should precede
T3, but I won't. Suppose that T1 has a MeLast in it, and neither T2 nor T3
does. Then some part of T1 - namely A0, B0, C0, and D0 - will come
early on, then parts of T2 and T3, and finally A1 will be last.
Similar situations hold for T2 and T3, but in all cases, A1 will be last,
assuming there are no other MeLast-like configurations in the T groups.
The intuition is gone.
Here is an example:
MeLast
|
X Y Z
\ | /
\|/
W
The New Flavors order is:
W,X,Y,A0,B0,C0,D0,Z,A1
The gabriel order is:
W,X,Y,A0,B0,C0,D0,A1,Z
Notice that in the gabriel order, the Y/MeLast guys are together
between Y and Z.
The existence of a MeLast configuration is purely an artifact of the
multiple passes that the New Flavors CPL computation does. If it had
a way to remember to redo A1 as soon as its predecessor, D0, was cleared
up, it would not need to make another pass through the lattice.
The MeLast configuration also proves that no algorithm based on
topological sort with a tiebreaker that is like a single-pass,
single-stack treewalk is equivalent to the New Flavors computation. I
haven't thought through the exact constraints, but preorder, reversed
reversed postorder, and things like that as the tiebreaker in conjunction
with topological sort cannot be the same as New Flavors, because they will
put classes in the groups T1, T2, and T3 together.
This increases the strength of my belief that the New Flavors algorithm is
not suitable for the CLOS standard.
-rpg-
(init)
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
(topologically-sort 'ptest1)
(print-nodes)
(let ((*walk-counter* 0)) (walk (find-node-record 'ptest1)))
;;; Hard Cases
(init)
(DEFCLASS A (B C D E F) ())
(DEFCLASS B (F X) ())
(DEFCLASS C (F Y) ())
(DEFCLASS D (F X) ())
(DEFCLASS E () ())
(DEFCLASS F () ())
(DEFCLASS X () ())
(DEFCLASS Y () ())
(topologically-sort 'a)
= (A B C D E F X Y)
(init)
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
(topologically-sort 'ptest1)
= (PTEST1 PTEST2 PTEST3 PTEST4 PTEST5)
(init)
(DEFCLASS PPTEST1 (PPTEST-MIXIN PPTEST2 PPTEST3) ())
(DEFCLASS PPTEST-MIXIN (PPTEST3) ())
(DEFCLASS PPTEST2 (PPTEST-INTERMEDIATE-1) ())
(DEFCLASS PPTEST3 (PPTEST-INTERMEDIATE-2) ())
(DEFCLASS PPTEST-INTERMEDIATE-1 (PPTEST-BASE) ())
(DEFCLASS PPTEST-INTERMEDIATE-2 (PPTEST-BASE) ())
(DEFCLASS PPTEST-BASE () ())
(topologically-sort 'pptest1)
= (PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
moon@stony-brook.scrc.symbolics.com/su
Tiebreaker
You're right, it looks encouraging. To make sure I have it right,
could you tell me what you get on this lattice for E1?
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
My reading of your algorithm says that we start:
e1 d1 d2 c1
At this point either c2 or c3 could come next. Scanning right to
left, d2 comes first, and so c3 is next, then c2. The final order
is:
e1 d1 d2 c1 c3 c2 top
I might be misreading your algorithm, so I'm simply asking for
confirmation. It's hard to know what is most intuitive in this case.
Also, if you could send some more examples, I'm trying to get a superfast
algorithm to do the CPL computation.
-rpg-
Common-Lisp-Object-system/su
CPL Tiebreaker
Ugh, bletch. I think I am really going to regret having written
this message. I think I found the tiebreaker. It passes all of
the hard intuitive cases, which I'll list below, along with all
of the cases ever mailed out.
The tiebreaker applies when there is more than one class with
no predecessors. The tiebreaker has two cases. The first case
is based on this reasoning by Danny (I'll paraphrase):
``If the user has a class and splits that class into two classes with no
other references to the direct superclass, there should be no chance of
any interaction with any other class used as a mixin. Hence one wants all
superclasses of a class to follow as soon as possible after the class they
are related to.''
This is very intuitive, and preorder treewalk is very intuitive. So
we do Danny's condition first and then preorder treewalk. Danny's
condition means this:
We define a relation called unique direct subclass. C is the unique direct
subclass of D if C is the only direct subclass of D. If class X was just
output and X is a unique direct subclass of some class D, D immediately
follows X. Otherwise, ties are broken by preorder treewalk (not
last-visited).
This means that we treat parts of the lattice that look like this:
\|/
D
|
C
/|\
as if they looked like this:
\|/
(D,C)
/|\
[Actually, the above picture is exactly how I looked when I discovered
this tiebreaker.]
Here are the hard cases:
(DEFCLASS A (B C D E F) ())
(DEFCLASS B (F X) ())
(DEFCLASS C (F Y) ())
(DEFCLASS D (F X) ())
(DEFCLASS E () ())
(DEFCLASS F () ())
(DEFCLASS X () ())
(DEFCLASS Y () ())
(topologically-sort 'a) = (A B C D E F X Y)
Well, this is simply preorder treewalk at work.
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
(topologically-sort 'ptest1) = (PTEST1 PTEST2 PTEST3 PTEST4 PTEST5)
In this one, PTEST3 is the unique direct subclass of PTEST4, so when
PTEST3 is output, PTEST4 and PTEST5 could come next. Preorder would
say PTEST5 is next, but Danny's rule overrides that.
(DEFCLASS PPTEST1 (PPTEST-MIXIN PPTEST2 PPTEST3) ())
(DEFCLASS PPTEST-MIXIN (PPTEST3) ())
(DEFCLASS PPTEST2 (PPTEST-INTERMEDIATE-1) ())
(DEFCLASS PPTEST3 (PPTEST-INTERMEDIATE-2) ())
(DEFCLASS PPTEST-INTERMEDIATE-1 (PPTEST-BASE) ())
(DEFCLASS PPTEST-INTERMEDIATE-2 (PPTEST-BASE) ())
(DEFCLASS PPTEST-BASE () ())
(topologically-sort 'pptest1)
= (PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
This one is nearly the same as the one before.
This addition condition adds no complexity to the algorithm, because
we compute the in-degrees of each class at DEFCLASS time.
-rpg-
(topologically-sort 'a)
(init)
(DEFCLASS A (B C D E F) ())
(DEFCLASS B (F X) ())
(DEFCLASS C (F Y) ())
(DEFCLASS D (F X) ())
(DEFCLASS E () ())
(DEFCLASS F () ())
(DEFCLASS X () ())
(DEFCLASS Y () ())
(defun test ()
(init)
(eval (subst () () '(defclass c1 (top) ())))
(eval (subst () () '(defclass c2 (top) ())))
(eval (subst () () '(defclass c3 (top) ())))
(eval (subst () () '(defclass d1 (c1 c2) ())))
(eval (subst () () '(defclass d2 (c1 c3) ())))
(eval (subst () () '(defclass e1 (d1 d2) ())))
(topologically-sort 'e1))
(init)
(defclass green-turtles (turtles green-things) ())
(defclass turtles (animate-things) ())
(defclass green-things (animate-things) ())
(topologically-sort 'green-turtles)
(init)
(defclass q (c d) ())
(defclass c (a b) ())
(defclass d (a b) ())
(defclass a (x)())
(defclass b (x) ())
(topologically-sort 'q)
common-lisp-object-system/su
CPL etc
After a day of meetings I was finally able to get back to our favorite
topic. Moon's tiebreaker variant admits a linear implementation, which is
pretty good. I have some questions about whether we think it is intuitive:
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
At some point Danny mentioned that the ``right'' order for this is
(E1 D1 D2 C1 C2 C3 TOP)
The new algorithm (and New Flavors, I think) produces
(E1 D1 D2 C1 C3 C2 TOP)
Is this less intuitive? More later.
Some people might have been confused by Moon's description. It read:
``When topological sort finds multiple candidates to go in next, choose the
candidate that has a direct subclass rightmost in the class precedence list
computed so far. ***If that subclass has more than one direct superclass
among the candidates, take the superclass that is most specific according
to the subclass's local precedence order.***''
The condition described in the sentence between the asterisks cannot
happen, so you shouldn't try to understand it. A candidate for
entering the final CPL has no predecessors, which means that all of its
siblings to the left have already been placed in the CPL, and so none of
them can be candidates to go next.
I think that in worrying about the CPL we have to keep in mind that most
people will operate under the following model: The direct superclasses
mentioned in the DEFCLASS form and their relative order are important. The
system will then provide some arbitrary total order, and the program will
have to be massaged until it works - simply because no one can understand
the algorithm. This is the model that KDO will have; KDO is no wimp.
Many people will wish they can simply supply their own ordering algorithm.
Here is a simple example, which many of you have seen before. There are 4
classes, perhaps poorly chosen:
Animate-things
blush-method = turn-pink
noseup-method = become-haughty
|
|
/ \
/ \
/ \
Turtles Green-animals
noseup-method = pick-up-pen blush-method = turn-purple
\ /
\ /
\ /
|
|
Green-turtles
Animate-things has two methods, blush-method and noseup-method. The effect of
the blush-method is to change colors and the effect of the noseup-method is
to change the attitude of the object to haughtiness. The first subclass is
Turtles, like LOGO turtles. The noseup-method shadows the animate-things method,
and the effect of it is to pick up the pen; the blush-method is ok. The second
subclass is Green-animals, and the blush-method is different, because when
a green thing turns pink, it really turns purple.
The final class is Green-turtles. This might be a dumb thing to do, but
the user's intuition might be reasonable. He sees that the Turtle noseup-method
is good, and that the Green-animals blush method is good, so he inherits from
both. But he has to mention Turtles and Green-animals in some order. If he
mentions them in the above order, he gets the wrong blush-method; if he reverses
them he gets the wrong noseup-method.
The solution is to reformulate the classes into more parts with hairy
relationships. A similar problem can happen when a user wants to inherit
slots. One can imagine an asymptotic situation where each DEFCLASS has
exactly one slot and you build your classes by the shopping cart method.
The user of the above class lattice believes that the CPL will reflect a
breadth-first CPL. The depth-first nature of all CPL computations so far
reflects a desire for ``transparency'' of subclass-superclass inheritance.
Perhaps we need to have a notation for inheriting from a set of
superclasses in no partocular order, which would signal the CPL
computation to go breadth-first. Maybe another partial solution is some
means of having generic functions be able to distinguish instances of
``this very class'' rather than instances of this very class or of its
subclasses.
In any event, what we are doing by defining the CPL computation as we
are is to provide a mechanism for people to curse the standard. Perhaps
it is necessary to have such a well-defined default, but maybe we should think
about a variety of alternatives from which the user can select as well
as an alternative to roll your own.
-rpg-
lgd/su
CONCEP.RPG
I've updated it from CONCEP.TEX as follows:
1. shared/local;clas/instance has been fixed
2. CPL description fixed.
3. defgeneric-options fixed throughout
4. proper name defined and used
5. (quote obj) => (eql obj) and used
6. generic-flet, generic-labels, generic-lambda introduced
7. type-of behavior defined
Things left to do that I noticed:
1. -setf flushed or not?
2. inheritance of slot descriptions
3. redefining classes
4. vote on extent of call-next-method?
5. Add Kempf to FUNCTI contributors list
Moon/su
Corrections
Ok, I've got the corrections in. Here are a few remaining questions
and comments:
\item{\bull} Otherwise, if the slot has an {\bf :initform} form, that form
is evaluated and the result is stored into the slot.
--> This is >only< done if the slot is uninitialized, according to what
we agreed on. A :before method could store into the slot, and in that
case the :initform would not override it, even though an initialization
argument would override it. Slightly strange, but it's what the group
converged on.
So, what's the best wording here? If we say ``otherwise, if the slot is
uninitialized and has....'' we are imprecise about where in the protocol
the :initform is taken into account. Do we want to say that if the slot is
uninitialized after the primary methods have a shot the :initform takes over?
Is it after all methods? Is it after initialize-instance?
On initialization arguments being multiply defined, I expanded the
bullets in that neighborhood to look like this. The reason is that
I wanted it clear that slot-fillers could be multiply-defined, that
method-implemented's could be multiply-defined, and that there was
no barrier between the names of slot-fillers and method-implemented's:
\item{\bull} It is valid for a single initialization argument to
initialize more than one slot if the same initialization argument name
appears in more than one {\bf :initarg} slot option.
\item{\bull} It is valid for a single initialization argument to appear
in more than one initialization method lambda-list.
\item{\bull} It is valid for a given initialization argument name to
appear both in an {\bf :initarg} slot option and in the lambda-list
of an initialization method.
``Should that be "uninitialized" or "unbound" slots or "slots that have no
values"?''
I want to avoid the term ``unbound slots'' to avoid having to discuss whether
there is such a thing as an unbound object and to avoid hinting at any
implementational questions.
moon/su
Varia
``GENERIC-LABELS and GENERIC-FLET are new special forms approved in
September. Their syntax resembles DEFGENERIC in exactly the way that the
syntax of LABELS and FLET resembles DEFUN.
[In the notes I have, the lambda-list is omitted, but that can't be
right since the :argument-precedence-order option depends on having
the lambda-list.]''
This was some sort of typo in the notes.
moon/su
Clarification
I am going through and doing your comments. In your comment:
``1-6 fourth paragraph: Clarify the range of n in the definition of
"superclass". I think you mean n >= 2, so that any "direct superclass"
is also a "superclass", but a class is not a superclass of itself.''
Could you check again that you think what I said is wrong? I think the
paragraph is right but possibly confusing. It says that Cn is a superclass
of C1 if there is a chain C2,...,Cn-1 where C2 is a direct superclass of
C1,...Cn is a direct superclass of Cn-1. The specification on i and n are
1 <= i < n, which means 2<=n.
Thanks. Should be done with most of your and Sonya's comments today.
-rpg-
common-lisp-object-system/su
Extent
Implementability is not the same as semantics. Methods are not functions.
(Methods include functions as parts. In fact, they can have generic
functions as parts.)
This debate is or ought to be about what methods are and what generic
functions are. Virtually all arguments I have seen that argue that
indefinite is correct also apply to TAGBODY's and GO's. If a method is
not a function, what is the etymology of ``CALL-NEXT-METHOD.''
Imagine a generic function with many methods - broken down into roughly
equal numbers of :around methods, :before methods, primary methods, and
:after methods. Suppose the generic function is invoked and after a couple
of primary methods are executed, a closure is thrown out that captures
CALL-NEXT-METHOD. Two years later someone stumbles across this closure and
FUNCALL's it. We're all happy to see the primary methods complete, and the
intended :after and :around methods ignored? (Of course, they didn't
complete the first time either, though the :before methods were executed.)
To me the execution of a generic function is a black box, just as TAGBODY
is. Because it is a black box, my understanding of the semantics of it
naturally includes the fact that CALL-NEXT-METHOD has ``hidden state.''
That is, to me an activation of a generic function includes imposing a
control structure on the methods and causing the functional objects
associated with methods to be invoked according to that control structure.
CALL-NEXT-METHOD is part of the control structure but not all of it. This
can be seen because the ``capturing of hidden state'' in my example does
not capture enough of the state to cause the generic function to complete.
If the method combination type were a linear CALL-NEXT-METHOD chain, the
effect would be the completion of the second part of the generic function.
Therefore, interrupting it strikes me as undesirable. Secondly, behavior
such as shown in my example strikes me as undesirable.
It is important for you to understand that my arguments about hidden state
follow from a decision about a principle - the black-box nature of the
execution of generic functions. They do not follow from imagining an
implementation and then reasoning about it. If you do not believe in the
black-box nature of the execution of generic functions, you will construct
arguments, semantics, and implementations that eliminate the hidden state.
If I were to accept the clear-box nature of generic function execution, I
would also explain the semantics with a nest of closures.
-rpg-
Moon/su
More Clarifications
I found these hard to understand:
1-23 last bullet: "(EQL -object-)" should be "(EQL -form-)", because
in a parameter specializer name, we have a form that is to be evaluated
to produce the object that appears in the parameter specializer. The
paragraph immediately following is wrong where it says "otherwise N
equals P" for this reason. We changed this when we changed QUOTE to EQL.
1-23 fourth paragraph: We no longer require parameter specializer names
to be Common Lisp type specifiers. (EQL -form-) is not a type-specifier.
If possible, could you rewrite the relevant parts of that section as makes
sense to clarify this for me? For example, the second comment seems to say
to flush the sentence that includes the two bullets, yes? What is the
precise relationship between parameter specializer names and Common Lisp
types?
-rpg-
moon/su
Clarifications
``1-32 first bullet last sentence: I don't understand why the word "only"
is present here. Maybe you mean "is supported only in :around methods
when a built-in" rather than "is supported in :around methods only when
a built-in"; i.e. does "only" modify ":around methods" or does it modify
"when"? Also, this sentence should probably be pulled out of the bullet
since I think it is saying something about both method roles. Maybe the
sentence should be deleted since the same information is repeated later
on the page.''
Well, the woman who wrote that is probably in the same building with
you. The sentence means that :around methods are only supported in
built-in combination types, not that only :around methods are supported.
I can make it say unambiguously what is meant, but maybe you should
confab with Sonya on that paragraph and its neighborhood.
-rpg-
common-lisp-object-system/su
Clear Versus Black Box
To the author of the generic function, the box is clear - but only during
that authorship. To the user it is black during execution. Therefore any
construct that opens a window into it is forbidden.
The actions of any FORTRAN program are well-defined. I believe we all
agree that FORTRAN was not well defined.
``I agree with Moon that the only reason not to publicize the name is to
allow implementtion freedom.''
If this would be the only reason, then the clarity of the box is
irrelevant.
-rpg-
common-lisp-object-system/su
Pavel's Comments
``Page 1-4, second set of bullets, second bullet -- Can't valid programs
rely on that error being signalled if they also specify (SAFETY 3)? I'm
generally unhappy with the phrase "at least in code compiled under one
compiler safety optimization level". I'd prefer a direct statement that
that level is 3.''
I don't to make CLOS depend on things that might change in Common Lisp
if I don't have to. Why state ``3'' when ``at least one'' will do?
``Page 1-5, third bullet -- What does the clause "but they must remain
undefined" mean? Does that mean that my implementation is incorrect if
I document just which nasty bug will crop up if situation S occurs? I
can't derive any useful content from this clause.''
As I mentioned in my message of July 8 containing the original proposal
which was accepted, this is to prevent implementations from using
the ``is an error'' out from Common Lisp. In Common Lisp, ``it is an
error'' means that no valid Common Lisp program should cause this situation
to occur and that the results are ``completely undefined.'' Steele goes on
to say that ``some particular implementation might ... define the effects and
results for such a situation.'' Steele mentions that ``must not'' means
``is an error.''
I have heard people argue as follows:
``It is an error to adjust an array that was not created with the
:adjustable argument non-nil. Therefore the results are undefined.
Therefore an implementation can define the behavior. Therefore, it is
ok to adjust an array created with the :adjustable argument nil.''
I want to prevent this. It's ok for your implementation to document that
the results are harmless, but I would prefer that you not state what they
are.
The other comments look good and duplicate a lot of Moon's comments, virtually
all of which are being incorporated. I expect the same will be true here.
Thanks, Pavel.
-rpg-
moon
Issues
0. functi.dvi is ready enough for the next go-around.
1. What is the story on the idea of built-in? Is this simply Danny's
way to get us to use the name for this concept he invented? Or does he
want to break up Steele's standard types into non-make-instanceable and
make-instanceable?
2. UPDATE-INSTANCE-STRUCTURE and CLASS-CHANGED needed to be parallel
in how and who does initialization. Danny proposes that default primary methods
handle it in both cases. My view is that unless there is some meta-object
way to eliminate the initialization step, the only way is by putting
them into a primary method that can be shadowed or eliminated.
In talking to Danny last night, I came to believe that he thinks there
would be no meta-object way to get at the initialization in this step.
3. What's the resolution on the CPL for NULL, SYMBOL, LIST et al?
4. What terminology for ``default primary method'' should we use?
5. Are methods side-effected when method functions change?
6. The reason that DEFMETHOD shouldn't specialize functions like CAR defaultly
is that the compiler has already compiled a pile of stuff knowing what's up.
WITH-ADDED-METHODS created lexical environment in which the compiler can know
all about that gives. Therefore, I think that if WITH-ADDED-METHODS is asked
to extend an ordinary function, it should make that function the method
function for the default primary method.
7. What about the class named OBJECT? How does it fit in?
8. If CALL-NEXT-METHOD is globally bound to a function that signals
an error, the name CALL-NEXT-METHOD has indefinite scope. Is this
what we mean to say?
By your comment about CALL-NEXT-METHOD's extent including the arguments
to the method, do you mean this:
(defmethod foo ((x1 c1) ... (xn Cn)
&optional (next-fun #'(lambda () (call-next-method))))...)
I guess this is ok.
-rpg-
common-lisp-object-system/su
Issues raised by comments on chapter 2
This message is about the format for description of generic functions
in chapter 2. The points are made as a response to a message that Danny
sent, but no one should interpret this as picking on his comments, which
simply serve to bring some decisions to light.
Danny writes:
``I think that if there is a method signature, there
should not be a section called Syntax. They are to some extent
redundant, and where they are not, Syntax was almost always wrong.''
Hm. I should have written the class redefinition section `wrong', then we
could have eliminated that too. Renaming ``Syntax'' to ``Generic Function
Syntax'' is useful when the generic function lambda-list is important to
know - that is, when it doesn't derive from the method lambda-lists.
Think of INITIALIZE-INSTANCE. And maybe it's generally useful for people
who are populating their CLOS with additional methods.
``<Add-method> This is the first example of the redundancy. Please take out
Syntax, and the first two sentences under Arguments....''
If I do that, here's the result:
******************************************************************************
Method Signatures:
add-method (generic-function standard-generic-function) (method standard-method)
Arguments:
The lambda-list of the method function must be congruent with the
lambda-lists of all other methods associated with the generic function and
with the lambda-list of the generic function, or else an error is
signaled.
******************************************************************************
Unfortunately, there is no method function mentioned. There is a larger
liklihood that this would mean the method function of the argument passed
to {\it method}, I suppose. A rewording of this could be:
``The lambda-list of the method function of the method object passed as
{\it method} must be congruent with the lambda-lists of all other methods
associated with the generic function and with the lambda-list of the
generic function, or else an error is signaled.''
One reason to describe the arguments in English is to introduce some
simple noun phrase to use to talk about these arguments.
Danny goes on:
``The signature specifies what the types of the arguments must be, and if
people add another method the arguments need not be those objects.''
This brings up the interesting point. We have a heading called ``Purpose:''.
Linda and I spent several hours last night trying to redesign the generic
function pages, and the question of when the purpose should be written as
the purpose of the generic function and when it should be the purpose
of some method. Here is an example, again ADD-METHOD.
****************************************************************************
Purpose:
The generic function add-method adds a method to a generic function. It
destructively modifies the generic function and returns the modified
generic function as its result.
****************************************************************************
ADD-METHOD has 1 method defined. This purpose could be moved to
describe the purpose of that method. If we do that, then any additional
methods are not constrained to have any particular behavior or purpose.
For instance, ADD-METHOD when applied to 2 matrices could add them - it
is the add method, after all.
The purpose when left as a description of the generic function requires
implementors to define only methods for ADD-METHOD that satisfy that
purpose.
The spirit of object-oriented programming, I guess, states that users can
define whatever the hell they like for methods. The spirit of reasonable
abstraction states that users should be required to choose their own
random names for their random methods, leaving ADD-METHOD for methods that
add methods to generic functions.
I propose, then, that the policy of CLOS be that purpose statements be promoted
to apply to generic functions whenever feasible.
Danny writes about CHANGE-CLASS:
``Remove Syntax section, Remove first two lines of Arguments. The last
sentence should read "... and then invokes the first method with the class
returned as value from (symbol-class symbol)."''
The last sentence cannot say this unless you are imagining that the
two methods on CHANGE-CLASS are defined as follows: Use LABELS to make
two functions, one that assumes a class as its second argument and one
that assumes a symbol as its second argument. Have the second invoke
the first (as a function) with (symbol-class symbol) as its second argument.
Now take these two functions and make method objects out of them with the
usual paraphenalia and stuff them into CHANGE-CLASS using ADD-METHOD.
I don't think this is what we mean. Therefore the purpose of the
second method must say something like:
``This method invokes CHANGE-CLASS on {\it instance} and (symbol-class
{\it symbol}).''
This is particularly relevant when the spirit of object-oriented programming
encourages us to write random methods for CHANGE-CLASS, and we certainly
want those methods to get a second crack at the instance in this case.
This brings up the second general point, which is are we going to require
that a pristine CLOS have all and only the methods described in the
specification? Danny's proposed rewrite of the description of CHANGE-CLASS
implies he believes so. I tend to favor the restriction.
Currently there is a statement in the introduction to Chapter 2 that
states:
``Any implementation of the \CLOS\ is allowed to provide other methods
for the generic functions described in this chapter.''
Opinions?
-rpg-
gregor.pa@xerox
Someone is Smoking Dope
I recall you went suborbital when I mentioned a discussion I had with
Steele on a topic of interest to CLOS. I invite you to string search for
it using ZMACS so that the comments you made to me will be fresh in your
mind.
Let's begin our odyssey of discovering the meaning and usage of ``comprise.''
Here is the offensive passage:
``A generic function object comprises a set of methods, a lambda-list, a
method combination type, and other information.''
Let's start with the definitions in the dictionaries I happen to have in
my office:
OED:
1. To lay hold on, take, catch, seize. (Obsolete)
1b. To seize under legal authority, attach.
2. To `take in' (mentally) perceive, comprehend, conceive (obsolete).
3. To bring together and comprehend or include, esp. in a treatise.
3b. esp. To comprehend compendiously; to sum up.
3c. To comprehend or include under or in a class or denomination.
4. Of things material: a. To take in within its space; to enclose, to hold
(obsolete).
4b. To contain as parts making up the whole , to consist of (the parts
specified).
4c. To extend so as to contain, to extend to, to cover a space or time.
5. Of things immaterial: a. To take in or include, as opposed to leaving out.
5b. To embrace as its contents, matter, or subject.
Definition 5a is probably the closest we can get to supporting your
argument. In my usage, what was left out? The phrase ``and other information''
covers all of that. Therefore, nothing was left out.
Let's try the Random House Second Edition (Unabridged):
1. To include or contain.
2. To consist of; be composed of.
3. To form or constitute.
They suggest ``include'' as a synonym.
Let's check their usage note:
``Comprise has an interesting history of sense development. In addition to
its original senses, dating from the 15th century, `to include' and `to
consist of', COMPRISE has had since the late 18th century the meaning `to form
or constitute'. Since the late 19th century <the passive is described>....''
This usage hints that the whole must be entirely made up of or be formed by
the listed parts. Again, my usage supports that.
Webster's Second (Unabridged)
1. <the same obsolete definition as OED's definition 1.>
2. To comprehend or include; to contain or cover compendiously, or as
constituent parts; sum up; cover.
3a. To consist or be made up of; as, his family COMPRISES five sons.
3b. To make up or constitute; as, the chapters that COMPRISE part 1.
Definition 3b implies that the parts should make up the entirety of
the whole, but their own definition 3a implies this is not necessary.
American Heritage (Oops!)
1. To consist of; be composed of.
2. To include; contain.
Usage (aha!) By definition the whole comprises the parts; the parts do
not comprise the whole, nor is the whole comprised of its parts.
In strict usage: `The Union comprises 50 states. Fifty states compose (or
constitute, make up) the Union. The Union is composed of 50 states.' This rule
restricting COMPRISE and COMPOSE is supported by a majority of the Usage Panel,
but returns indicate that COMPRISE is increasingly used in both senses....''
Hm, the point is that `the parts comprise the whole' is gaining usage. This
doesn't seem to talk at all about the point you were trying to make.
Well, let's look at ``A Dictionary of Modern English Usage,'' by H.W.Fowler.
This is hard to read, so I synopsize:
One major point is that COMPRISE and COMPOSE are confused based on
whether wholes COMPOSE or COMRPISE the parts. The other major point is
that COMRPISE and INCLUDE are distinct. COMPRISE means that all the parts
are mentioned, while INCLUDE doesn't.
My usage, though it uses an escape clause, mentions all the parts.
This is boring. I think the point you were trying to make was that
one could use COMPRISE only when the parts were a necessary part of the
whole, so that removing a part would cause the identity of the whole to
evaporate. No one here mentions that aspect. In fact, some of the
examples (like the family example) don't support that at all.
However, for fun let's suppose you are right. Is there such a thing
as a standard generic function without all these parts? You say `yes',
and I say `no.'
Here is a dumb example:
(defclass 2-dimenional-point ()
((x :initform 0) (y)))
(setq p (make-instance '2-dimensional-point))
rpg: p is a 2-dimensional-point.
Gregor: p is not a 2-dimenional-point because an initial value for y is
not supplied.
Well, maybe what happened (let me paraphrase) is that in your discussion
with your friend, you didn't explain the facts as objetively as you
thought you did, and he was unable to comment accurately on the issue.
-rpg-
common-lisp-object-system/su
State of Affairs
I've completed the major pass on chapter 1 that Gregor's comments
required. The result so cleaned it up that I made a second major
pass and I now believe chapter 1 to be very close to complete.
The state of affairs with chapter 2 now greatly concerns me.
To illustrate this, let me comment on one of the comments that Moon
made about the selected function pages that we put out for comment.
Regarding CHANGE-CLASS Moon writes:
``change-class: the second remarks paragraph is a remark about the
generic function as a whole, and has nothing to do with the specific
method to which it is attached.''
That remarks paragraph states:
``This method on {\bf change-class} has several semantic difficulties.
First, it performs a destructive operation that can be invoked within a
method on an instance that was used to select that method. When multiple
methods are involved because methods are being combined,
the methods currently executing or about to be executed
may no longer be applicable. Second, some implementations might use compiler
optimizations of slot access, and when the class of an instance is
changed the assumptions the compiler made might be violated.
This implies that a programmer must not use this method on {\bf
change-class} inside a method if any methods for that generic function
access any slots, or else the results are undefined.''
The semantic problem is that the class of the instance is altered while
the generic function is operating. One can argue that this is a change of
identity in some semantic domain. The fact that this is related to a
``destructive operation'' depends on the representation of the instance,
which depends on its metaclass which depends on the fact that the instance
is an instance of standard-object, because its class is standard-class.
This appears to be something specific to this method or constellation of
methods. The same reasoning holds for the mention of the compiler messing
around with optimizations of slot access - I've heard some metaclasses
say ``what's a slot?''
Therefore, the semantic difficulty is best expressed in both places:
There is a semantic difficulty with the generic function because we choose
to specify that whatever else it does it alters the class of an instance.
And this can happen in the middle of a method combination that might
involve running those other methods on a now-non-applicable instance.
This method happens to compound the problem by messing with the
representation in some way, invalidating the compiler's assumptions.
Therefore, the comment Moon makes serves to raise a much harder issue of
how close to the bone we cut our distinctions.
Notice that LGD and I gave this some amount of thought, because the
Purpose entry for the generic function states that the generic function
changes the class, while the one for this main method talks about the
destructiveness of the operation.
What has to be pointed out is that even if we choose to back out of
any changes made to the format of chapter 2 in the last 4 days (this amounts
to little or no work), we now know that the wording that we have been using
is very imprecise with respect to a level of precision to which we could
rationally aspire. This Remark, if left in a version of chapter 2 with
the older format, mixes up the general activities and meaning of a very
abstract entity (a generic function) with the activities and meaning of
a specific method.
Let me state at this point that LGD and I have neither interest nor motivation
to want to take a shot at sorting this out by ourselves. And I can easily
see this group, even in a face-to-face meeting, arguing for weeks about
the wording and exact breakdown of what is said when and where.
What's worse, our selection procedure was to pick the first 4 or 5
function pages in chapter 2 to try, not the hardest 4 or 5, and I'm not
sure that we could totally resolve CHANGE-CLASS in under 4 days of
discussion at the current bandwidth.
Therefore, I leave it to you folks to decide how to proceed.
-rpg-
gregor.pa@xerox/su
Review material
I put together a first attempt of a description of meta-objects for
chapter 1 along with a redo of the meta-objects section. I'm not
entirely sure that the result is clear or accurate. It appears at the
end of this message. Also, could you review the chapter 1 sections on
change-class and class redefinition? I attempted a simplifying rewrite
and found the original (written by Moon) to be ambiguous. Thanks.
-rpg-
\beginSection{Meta-Objects}
The implementation of the \OS\ manipulates metaclasses and invokes
generic functions. The meta-object protocol specifies a set of generic
functions defined by methods on objects; the behavior of those generic
functions defines the behavior of the \OS. The generic functions and
the objects on which their methods are specialized are called {\bit
meta-objects}. Programming at the meta-object protocol level involves
defining new objects along with methods specialized on them for
generic functions specified to be in the meta-object protocol.
\beginsubSection{Metaclasses}
The {\bit metaclass\/} of an object is the class of its class. The
metaclass determines the representation of instances of its instances and
the forms of inheritance used by its instances for slot descriptions and
method inheritance. The metaclass mechanism can be used to provide
particular forms of optimization or to tailor the \CLOS\ for particular
uses. The protocol for defining metaclasses is discussed in the chapter,
``The \CLOS\ Meta-Object Protocol.''
\endsubSection%{Metaclasses}
\beginsubSection{Standard Metaclasses}
The \CLOS\ provides a number of predefined metaclasses. These include the
following: {\bf standard-class}, {\bf built-in-class}, and {\bf
structure-class}.
\beginlist
\item{\bull}
The class {\bf standard-class} is the default class of classes defined
by {\bf defclass}.
\item{\bull} The class {\bf built-in-class} is the class whose
instances are classes that have special implementations with
restricted capabilities. All classes that correspond to the standard
Common Lisp types specified in {\it Common Lisp: The Language\/}
are potentially instances of {\bf built-in-class}.
The predefined Common Lisp type specifiers that are required to have
corresponding classes are listed in Figure~1-1. It is implementation
dependent whether each of these classes is actually a built-in class.
\item{\bull}
All classes defined by means of {\bf defstruct} are instances of
{\bf structure-class}.
\endlist
\endsubSection%{Standard Metaclasses}
\beginsubSection{Standard Meta-objects}
The class {\bf standard-object} and instances of the classes {\bf
standard-method} and {\bf standard-generic-function} are standard
meta-objects.
{\bf standard-object}.
\beginlist
\item{\bull}
The class {\bf standard-method} is the default class of methods
defined by {\bf defmethod}.
\item{\bull}
The class {\bf standard-generic-function} is the default class of
generic functions defined by the method-defining forms {\bf defmethod},
{\bf defgeneric}, {\bf generic-function}, {\bf generic-flet},
{\bf generic-labels}, and {\bf with-added-methods}.
\item{\bull} The class named {\bf standard-object} is an instance of
the class {\bf standard-class} and is a superclass of every class that
is an instance of {\bf standard-class} except itself.
\endlist
\endsubSection%{Standard Meta-objects}
\endSection%{Meta-Objects}
common-lisp-object-system/su
Remarks about Comments on Latest Draft Documents
The name of a class is restricted to be a symbol in chapter 1, and that
text has been there for a long time. That restriction appears in the
paragraph about proper names. As you recall, that paragraph was discussed
at great length in person and by netmail during rounds of review of the
chapters earlier this fall. Apparently no one thought to criticize the
restriction at that point.
The restriction and the implementation of the restriction are two
different topics.
I believe the restriction is fine, and I am also perturbed that
sections of the specification that have been reviewed extensively
are often subject to later changes. At some point we need to
decide that something is final so that the entire document can be
made consistent. Linda was simply trying to make the descriptions in
chapter 2 coincide with statements in chapter 1.
At this point I believe that compelling arguments must be made for even
small changes. There is no tradition of using non-symbols for names in
Lisp. Non-symbols are used as keys for various purposes, but not as names.
Defstruct restricts names to symbols. Therefore, I can see no compelling
reason to break the tradition and allow non-symbols to be the names of
classes.
I do not find silly the use of parameter specializers to do typechecking.
I find it hard to imagine what sort of argument one could make to show
that point of view. That issue is different from the one about whether we
ought to use parameter specializers in the document for that purpose. On
this point I suppose it is better to simply state the restrictions in
English in the remarks. Therefore, I suggest that chapter 2 reflect
chapter 1 on this point in the remarks. saying that the parameter
specializer for the new value is T.
On the topic of the DOCUMENTATION generic function, my opinion is that the
remarks ought to state in English the restriction that the new value in a
SETF of DOCUMENTATION must be a string or it must be NIL to signify that
the association between any existing documentation and the object in
question must be eliminated. This restriction is stronger than any that
can be conservatively deduced from CLtL, though it is not stronger can be
reasonably deduced.
The following reasoning was stated against this restriction:
CLtL doesn't say anywhere what values are allowed, but a
reasonable inference is that NIL is allowed, and "documentation
information" might have been meant to include some sort of
structures as well.
CLtL states four times that strings are the things that are associated
with symbols as documentation. It never states that anything else can be
associated with symbols as documentation. CLtL does state that the
function DOCUMENTATION will return NIL if no documentation exists. The
statement ``SETF may be used with DOCUMENTATION to update documentation
information'' in the context of the documentation section and the section
on SETF does not imply anything about the types of new values, but it
similarly does not imply anything about the nature of the update except
that whatever happens, DOCUMENTATION returns a string or NIL. So if a
structure is given as the new value in a SETF expression, DOCUMENTATION
will return a string or NIL - one cannot be sure that if it returns a
string that the string is related to the structure.
It is reasonable to conclude that NIL can be given to SETF of DOCUMENTATION,
but the reasonable conclusion about the effect of this is to remove any
association between an existing documentation string and the symbol.
I therefore favor introducing the restriction.
-rpg-
rrrs-authors@mc.lcs.mit/su
CLOS Error Terminology
The following is the current section on error terminology in the CLOS
document. I should point out that this section is currently
under debate. The areas of debate are the definitions of ``undefined''
and ``unspecified,'' along with the general philosophy that extensions
are disallowed by default (which is the opposite to Common Lisp):
\beginSection{Error Terminology}
The terminology used in this document to describe erroneous
situations differs from the terminology used in {\it Common Lisp:
The Language}, by Guy L. Steele Jr. This terminology involves {\bit
situations}; a situation is the evaluation of an expression in some
specific context. For example, a situation might be the invocation of
a function on arguments that fail to satisfy some specified
constraints.
In the specification of the \CLOS, the behavior of programs in all situations
is described, and the options available to the implementor are defined. No
implementation is allowed to extend the syntax or semantics of the \OS\ except
as explicitly defined in the \OS\ specification. In particular, no
implementation is allowed to extend the syntax of the \OS\ in such a way that
ambiguity between the specified syntax of \OS\ and those extensions is
possible.
``When situation $S$ occurs, an error is signaled.''
This terminology has the following meaning:
\beginlist
\item{\bull} If this situation occurs, an error will be signaled in
the interpreter and in code compiled under all compiler safety
optimization levels.
\item{\bull} Valid programs may rely on the fact that an error will be
signaled in the interpreter and in code compiled under all compiler
safety optimization levels.
\item{\bull} Every implementation is required to detect such an error
in the interpreter and in code compiled under all compiler safety
optimization levels.
\endlist
``When situation $S$ occurs, an error should be signaled.''
This terminology has the following meaning:
\beginlist
\item{\bull} If this situation occurs, an error will be signaled at
least in the interpreter and in code compiled under the safest
compiler safety optimization level.
\item{\bull} Valid programs may not rely on the fact that an error will be
signaled.
\item{\bull} Every implementation is required to detect such an error
at least in the interpreter and in code compiled under the safest
compiler safety optimization level.
\item{\bull} When an error is not signaled, the results are undefined (see
below).
\endlist
``When situation $S$ occurs, the results are undefined.''
This terminology has the following meaning:
\beginlist
\item{\bull} If this situation occurs, the results are unpredictable. The
results may range from harmless to fatal.
\item{\bull} Implementations are allowed to detect this situation and
signal an error, but no implementation is required to detect the
situation.
\item{\bull} No valid program may depend on the effects of this
situation, and all valid programs are required to treat the effects
of this situation as unpredictable.
\endlist
``When situation $S$ occurs, the results are unspecified.''
This terminology has the following meaning:
\beginlist
\item{\bull} The effects of this situation are not specified in
the \OS, but the effects are harmless.
\item{\bull} Implementations are allowed to specify the effects of
this situation.
\item{\bull} No portable program can depend on the effects of this
situation, and all portable programs are required to treat the situation
as unpredictable but harmless.
\endlist
``The \CLOS\ may be extended to cover situation $S$\negthinspace.''
The meaning of this terminology is that an implementation is free to treat
situation $S$ in one of three ways:
\beginlist
\item{\bull} When situation $S$ occurs, an error is signaled at least
in the interpreter and in code compiled under the safest compiler
safety optimization level.
\item{\bull} When situation $S$ occurs, the results are undefined.
\item{\bull} When situation $S$ occurs, the results are defined and
specified.
\endlist
In addition, this terminology has the following meaning:
\beginlist
\item{\bull} No portable program can depend on the effects of this
situation, and all portable programs are required to treat the situation
as undefined.
\endlist
``Implementations are free to extend the syntax $S$\negthinspace.''
This terminology has the following meaning:
\beginlist
\item{\bull} Implementations are allowed to define unambiguous extensions
to syntax $S$\negthinspace.
\endlist
The \CLOS\ specification may disallow certain extensions while allowing others.
\endSection%{Error Terminology}